package cn.edu.jxau.test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * 排序算法的稳定性测试
 * 
 * @author 付大石
 */

public class Main {

    public static void main(String[] args) {

        String[] domainArr = { "cs.princeton.edu", "jxau.edu.cn", "tsinghua.edu.cn", "pku.edu.cn", "baidu.com",
                "alibaba.com", "apache.org" };
        sort(domainArr);
        System.out.println(Arrays.toString(domainArr));
    }

    private static <T extends Comparable<T>> void sort(T[] arr) {
        sort(arr, 0, arr.length - 1);
    }

    private static <T extends Comparable<T>> void sort(T[] arr, int low, int high) {

        if (high <= low) {
            return;
        }
        int p = partition(arr, low, high);
        sort(arr, low, p - 1);
        sort(arr, p + 1, high);
    }

    private static <T extends Comparable<T>> int partition(T[] arr, int low, int high) {

        T p = arr[low]; // 切分元素
        while (low < high) {
            while (low < high && p.compareTo(arr[high]) < 0) {
                high--;
            }
            if (low < high) {
                arr[low] = arr[high];
                low++;
            }
            while (low < high && p.compareTo(arr[low]) > 0) {
                low++;
            }
            if (low < high) {
                arr[high] = arr[low];
                high--;
            }
        }
        arr[low] = p;
        return low;
    }
}

class Domain implements Comparable<Domain> {

    private String domain; // 域名
    private String[] reverseDomain; // 逆域名

    public Domain(String domain) {
        this.domain = domain;
        String[] domainArr = domain.split("\\.");
        for (int i = 0; i < domainArr.length / 2; i++) { // 逆序域名
            String temp = domainArr[i];
            domainArr[i] = domainArr[domainArr.length - i - 1];
            domainArr[domainArr.length - i - 1] = temp;
        }
        this.reverseDomain = domainArr;
    }

    @Override
    public int compareTo(Domain d) {

        String[] arr1 = reverseDomain;
        String[] arr2 = d.reverseDomain;
        int lim = Math.min(arr1.length, arr2.length);
        for (int i = 0; i < lim; i++) {
            int cmp = arr1[i].compareTo(arr2[i]);
            if (cmp != 0) {
                return cmp;
            }
        }
        return arr1.length - arr2.length;
    }
}